Kurs szybkiego czytania

Limit pamięci: 128 MB

Bajtazar zapisał się na kurs szybkiego czytania, na którym nauczył się wielu ćwiczeń poprawiających spostrzegawczość. Jego ulubionym ćwiczeniem jest znajdowanie wzorca w ciągu symboli. Aby przygotować ćwiczenie, Bajtazar wykorzystuje komputer do wygenerowania bardzo długiego ciągu zer i jedynek. Wybiera liczby , , , takie, że i są względnie pierwsze, a komputer generuje ciąg , gdzie wtedy i tylko wtedy, gdy . Następnie Bajtazar wymyśla drugi, krótszy ciąg symboli . Jego zadaniem jest jak najszybsze znalezienie wszystkich wystąpień krótszego ciągu w ciągu wygenerowanym przez komputer. Ciebie poprosił o pomoc w napisaniu programu, który sprawdzi, czy znalazł wszystkie.

Wejście

Pierwszy wiersz standardowego wejścia zawiera pięć liczb całkowitych , , , i (, , ) pooddzielanych pojedynczymi odstępami. Liczby i są względnie pierwsze. W drugim wierszu zapisane jest jedno -literowe słowo złożone z symboli 0 i 1.

Istnieją następujące, rozłączne grupy testów:

• w testach wartych punktów zachodzi warunek ;
• w innych testach wartych punktów zachodzi warunek ;
• w jeszcze innych testach wartych punktów zachodzi warunek .

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać liczbę całkowitą, będącą liczbą wystąpień ciągu w ciągu .

Przykład

Dla danych wejściowych:

9 5 6 4 3
101

poprawną odpowiedzią jest:

3

Wyjaśnienie do przykładu: Dla , , i komputer wygeneruje ciąg zgodnie z poniższą tabelką:

Ciąg 101 występuje trzy razy w ciągu 101011010.

Testy "ocen":

• 1ocen: szukamy wystąpień ciągu 0010 w ciągu 10010000100100100100;
• 2ocen: szukamy wystąpień ciągu 00000 w ciągu 0000000100000001000000000000001;
• 3ocen: , . Szukamy wystąpień ciągu 011...11 (cyfra oraz same jedynki) w ciągu 00...0011...110 ( zer, jedynek, zero).

Autor zadania: Wojciech Rytter.